// https://www.lintcode.com/problem/repeated-dna/description
// 774. 重复
// 所有的DNA由一系列缩写的核苷酸 A, C, G 和 T组成.
// 比如; "ACGAATTCCG". 在研究 DNA 时, 有时候鉴别出 DNA 中的重复序列是很有用的.
// 写一个函数来找到所有在 DNA 中出现超过一次且长度为 10个字母 的序列(子串).

// 样例
// 给出 S = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",
// 返回 ["AAAAACCCCC", "CCCCCAAAAA"].



class Solution {
public:
    /**
     * @param s: a string represent DNA sequences
     * @return: all the 10-letter-long sequences 
     */
    // vector<string> findRepeatedDna(string &s) {
    //     // write your code here
    //     map<string, int> seq_map;
    //     vector<string> result;
    //     if (s == "")
    //     {
    //         return result;
    //     }
        
    //     // 输入
    //     // ""
    //     // 期望答案
    //     // []
    //     // 为什么报错？
        
    //     for (int i = 0; i <= s.length() - 10; i++)
    //     {
    //         seq_map[s.substr(i, 10)]++; // c++ substr第二个参数是个数，别搞错了！
    //     }
    //     for (int i = 0; i <= s.length() - 10; i++)
    //     {
    //         string tmp = s.substr(i, 10);
    //         if (seq_map[tmp] > 1)
    //         {
    //             if(find(result.begin(), result.end(), tmp) == result.end())
    //             {
    //                 result.push_back(tmp);
    //             }
    //         }
    //     }
    //     return result;
    // }
    
    // 法二：
    vector<string> findRepeatedDna(string &s) {
        vector<string> result;
        if (s == "")
        {
            return result;
        }
        set<string> set1;
        set<string> set2;
        for (int i = 0; i <= s.length() - 10; i++)
        {
            string tmp = s.substr(i, 10);
            if (!set1.insert(tmp).second)
            {
                set2.insert(tmp);
            }
        }
        copy(set2.begin(), set2.end(), std::back_inserter(result));
        return result;
    }
};